#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>

using namespace std;

//class Solution
//{
//public:
//    string longestPalindrome(string s)
//    {
//        int begin = 0;
//        int len = 0;
//        int n = s.size();
//        for (int i = 0; i < n; i++)
//        {
//            int left = i;
//            int right = i;
//            while (left >= 0 && right < n && s[left] == s[right])
//            {
//                left--;
//                right++;
//            }
//            if (right - left - 1 > len)
//            {
//                begin = left + 1;
//                len = right - left - 1;
//            }
//
//            left = i;
//            right = i + 1;
//            while (left >= 0 && right < n && s[left] == s[right])
//            {
//                left--;
//                right++;
//            }
//            if (right - left - 1 > len)
//            {
//                begin = left + 1;
//                len = right - left - 1;
//            }
//        }
//
//        return s.substr(begin, len);
//    }
//};
//
//int main()
//{
//    Solution s;
//    s.longestPalindrome("babad");
//    return 0;
//}



//class Solution
//{
//public:
//    bool canConstruct(string ransomNote, string magazine)
//    {
//        unordered_map<char, int> r_map;
//        unordered_map<char, int> m_map;
//
//        for (int i = 0; i < ransomNote.size(); i++)
//        {
//            r_map[ransomNote[i]]++;
//        }
//        for (int i = 0; i < magazine.size(); i++)
//        {
//            m_map[magazine[i]]++;
//        }
//
//        auto it = r_map.begin();
//        while (it != r_map.end())
//        {
//            if (!(m_map.count(it->first) && m_map[it->first] >= it->second))
//            {
//                return false;
//            }
//            it++;
//        }
//
//        return true;
//    }
//};


class Solution
{
public:
    string convert(string s, int numRows)
    {
        if (numRows == 1)
            return s;

        string ret;
        int n = s.size();
        int d = numRows * 2 - 2;

        for (int i = 0; i < n; i += d)
        {
            ret += s[i];
        }
        for (int i = 1; i < numRows - 1; i++)
        {
            for (int k = i, j = d - k; k < n || j < n; k += d, j += d)
            {
                if (k < n)
                    ret += s[k];
                if (j < n)
                    ret += s[j];
            }
        }
        for (int i = numRows - 1; i < n; i += d)
        {
            ret += s[i];
        }

        return ret;
    }
};
